{
"cells": [
{
"cell_type": "markdown",
"metadata": {},
"source": [
"*[Lab 4, CS206: Data Structures, Bryn Mawr College. In the following cell, give a hash title and by-line. Then you can remove this cell. This lab is due in one week.]*"
]
},
{
"cell_type": "markdown",
"metadata": {
"nbgrader": {
"grade": true,
"grade_id": "title",
"locked": false,
"points": 10,
"solution": true
}
},
"source": []
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# BinaryTrees and Sorting\n",
"\n",
"This lab will explore searching binary trees and sorting arrays of integers.\n",
"\n",
"## BinaryTree search\n",
"\n",
"1. In the last lab, you wrote a sorted binary tree. For the following, test out your search on the following sized trees:\n",
"* Put 100 million items in the tree, in order. \n",
"* Put 1,000 million items in the tree, in order. \n",
"* Put 100,000 million items in the tree, in order. \n",
"* Put 1 million items in the tree, in order. \n",
"2. Run your find() method to find items that are, and are not in the tree.\n",
"3. Create a table showing:\n",
"\n",
"Tree Size | Comparisons to Find Item in tree | Comparisons to Find Item not in tree\n",
"----------| --------------------------------- | ------------------------------------\n",
"100 | |\n",
"1,000 | |\n",
"100,000 | |\n",
"1,000,000 | |\n",
"\n",
"Your numbers should be an average.\n",
"\n",
"Put your code here for your Binary tree, find, and None. You may copy your code from last week. If you didn't get last week's answer, ask and a solution will be provided."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": true,
"nbgrader": {
"grade": true,
"grade_id": "binary-tree-search",
"locked": false,
"points": 50,
"solution": true
}
},
"outputs": [],
"source": []
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"You can add cells here to compute your table values. You can use the process below for making random integers for putting into your tree."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": []
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Put your table here:"
]
},
{
"cell_type": "markdown",
"metadata": {
"collapsed": true,
"nbgrader": {
"grade": true,
"grade_id": "binary-tree-table",
"locked": false,
"points": 50,
"solution": true
}
},
"source": []
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Sorting\n",
"\n",
"Shifting gears, we will look at three sorting algorithms, and compare how \"good\" they are.\n",
"\n",
"### Double Trouble\n",
"\n",
"Perhaps one of the simplest methods of sorting a list of numbers is the \"Double Trouble\" algorithm:\n",
"\n",
"1. For each number $i$ in the array, \n",
"2. compare it to every other number $j$ in the array\n",
" * if number[$i$] > number[$j$], then swap them"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Let's write that algorithm. First we need an array of numbers."
]
},
{
"cell_type": "code",
"execution_count": 3,
"metadata": {
"collapsed": false
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"| Added variable my_array of type int[]\n",
"\n"
]
}
],
"source": [
"int[] my_array;"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Let's write some functions to create lengths of random numbers:"
]
},
{
"cell_type": "code",
"execution_count": 4,
"metadata": {
"collapsed": false
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"\n"
]
}
],
"source": [
"import java.lang.Math;"
]
},
{
"cell_type": "code",
"execution_count": 8,
"metadata": {
"collapsed": false
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"\n",
"\n",
"| Added method printArray(int[])\n",
"\n"
]
}
],
"source": [
"int[] makeArray(int size, int low, int high) {\n",
" int[] array = new int[size];\n",
" for (int i=0; i < size; i++) {\n",
" array[i] = (int)((Math.random() * (high - low)) + low);\n",
" }\n",
" return array;\n",
"}\n",
"\n",
"void printArray(int[] array) {\n",
" for (int i=0; i < array.length; i++) {\n",
" printf(\"%s, \", array[i]);\n",
" }\n",
" printf(\"\\n\");\n",
"}"
]
},
{
"cell_type": "code",
"execution_count": 9,
"metadata": {
"collapsed": false
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"47, 56, 19, 1, 73, 75, 85, 96, 89, 18, \n",
"\n"
]
}
],
"source": [
"printArray(makeArray(10, 0, 100))"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Now, let's sort the list using the Double Trouble algorithm.\n",
"\n",
"* It should sort the numbers *in place*\n",
"* Smallest to largest\n",
"\n",
"Use these functions to count the compares:\n",
"\n",
"```java\n",
"int compares = 0; // global\n",
"\n",
"void swap(int[] array, int i, int j) {\n",
" int temp = array[i];\n",
" array[i] = array[j];\n",
" array[j] = temp;\n",
"}\n",
"\n",
"boolean compare(int v1, int v2) {\n",
" compares++;\n",
" return v1 > v2;\n",
"}\n",
"\n",
"int sort_double_trouble(int[] array) {\n",
" compares = 0;\n",
" /// Write code here!\n",
" return compares;\n",
"}\n",
"```"
]
},
{
"cell_type": "code",
"execution_count": 14,
"metadata": {
"collapsed": false,
"nbgrader": {
"grade": true,
"grade_id": "double-trouble",
"locked": false,
"points": 50,
"solution": true
}
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"\n",
"| Modified variable compares of type int with initial value 0\n",
"\n",
"\n",
"| Modified method swap(int[],int,int)\n",
"| Update overwrote method swap(int[],int,int)\n",
"\n",
"\n",
"\n",
"\n",
"\n"
]
}
],
"source": [
"\n",
"int compares = 0; // global\n",
"\n",
"void swap(int[] array, int i, int j) {\n",
" int temp = array[i];\n",
" array[i] = array[j];\n",
" array[j] = temp;\n",
"}\n",
"\n",
"boolean compare(int v1, int v2) {\n",
" compares++;\n",
" return v1 > v2;\n",
"}\n",
"\n",
"int sort_double_trouble(int[] array) {\n",
" compares = 0;\n",
" for (int i=0; i < array.length - 1; i++) {\n",
" for (int j=i; j < array.length; j++) {\n",
" if (compare(array[i], array[j])) {\n",
" swap(array, i, j);\n",
" }\n",
" }\n",
" }\n",
" return compares;\n",
"}"
]
},
{
"cell_type": "code",
"execution_count": 17,
"metadata": {
"collapsed": false
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"| Modified variable array1 of type int[] with initial value [I@50cbc42f\n",
"\n",
"25, 50, 16, 88, 73, 33, 20, 23, 12, 71, \n",
"\n",
"Double Trouble took 54 comapres\n",
"\n",
"12, 16, 20, 23, 25, 33, 50, 71, 73, 88, \n",
"\n"
]
}
],
"source": [
"int[] array1 = makeArray(10, 0, 100);\n",
"printArray(array1);\n",
"printf(\"Double Trouble took %s comapres\\n\", sort_double_trouble(array1));\n",
"printArray(array1);"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Bubble Sort\n",
"\n",
"Perhaps a \"better\" algorithm is Bubble sort.\n",
"\n",
"It works as follows:\n",
"\n",
"1. Let k = 1\n",
"2. For each number $i$ in the array (up to length - k), \n",
"3. compare it to the next number $j$ in the array\n",
" * if number[$i$] > number[$j$], then swap them\n",
"4. Increment k\n",
"3. Go back to step 1, until no more swaps were made\n",
"\n",
"It is called Bubble sort, because the biggest number will bubble up to the top on the first loop, then the second largest number on the second loop, etc.\n",
"\n",
"Write the Bubble sort algorithm, and test it.\n"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": true,
"nbgrader": {
"grade": true,
"grade_id": "bubble-sort",
"locked": false,
"points": 50,
"solution": true
}
},
"outputs": [],
"source": []
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Quicksort\n",
"\n",
"The final algorithm that we will look at is quicksort. quicksort represents a class of algorithms in computer science that capture the motto \"divide and conquer\".\n",
"\n",
"The quicksort algorithm:\n",
"\n",
"\n",
"Pick a pivot value\n",
"Break set of items into two parts:\n",
" first part is all less than the pivot value\n",
" second part is all greater than the pivot value\n",
"Sort the first part\n",
"Sort the second part\n",
"\n",
"\n",
"The quicksort algorithm, with more implementation details:\n",
"\n",
"\n",
"Quicksort on start and end:\n",
" if start less than end:\n",
" Partition from start to end around p:\n",
" Quicksort on start and p - 1\n",
" Quicksort on p and end\n",
"\n",
"\n",
"The partition picks a point, \n",
"\n",
"\n",
"Partition from start to end:\n",
" Pick a pivot position, p, and pivot value\n",
" Partition array into:\n",
" those less than pivot value\n",
" pivot value\n",
" those less than pivot value\n",
" return partition\n",
"\n",
"\n",
"In Java, the main quicksort function looks like:\n",
"\n",
"```java\n",
"void quicksort(int[] array, int lo, int hi) {\n",
" if (lo < hi) {\n",
" int p = partition(array, lo, hi);\n",
" quicksort(array, lo, p - 1);\n",
" quicksort(array, p + 1, hi);\n",
" }\n",
"}\n",
"\n",
"int partition(int[] array, int lo, int hi) {\n",
" int pivotIndex = choosePivot(lo, hi);\n",
" int pivotValue = array[pivotIndex];\n",
" // put the chosen pivot at array[hi]\n",
" swap(array, pivotIndex, hi);\n",
" int storeIndex = lo;\n",
" // Compare remaining array elements against pivotValue = array[hi]\n",
" for (int i = lo; i <= hi - 1; i++) {\n",
" if (compare(pivotValue, array[i])) {\n",
" swap(array, i, storeIndex);\n",
" storeIndex = storeIndex + 1;\n",
" }\n",
" }\n",
" swap(array, storeIndex, hi); // Move pivot to its final place\n",
" return storeIndex;\n",
"}\n",
"\n",
"int choosePivot(int lo, int hi) {\n",
" return (int)Math.ceil((hi + lo) / 2);\n",
"}\n",
"```"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"In the next cell, implement the quicksort algorithm."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": true,
"nbgrader": {
"grade": true,
"grade_id": "quick-sort",
"locked": false,
"points": 50,
"solution": true
}
},
"outputs": [],
"source": [
"void quicksort(int[] array, int lo, int hi) {\n",
" if (lo < hi) {\n",
" int p = partition(array, lo, hi);\n",
" quicksort(array, lo, p - 1);\n",
" quicksort(array, p + 1, hi);\n",
" }\n",
"}\n",
"\n",
"int partition(int[] array, int lo, int hi) {\n",
" int pivotIndex = choosePivot(lo, hi);\n",
" int pivotValue = array[pivotIndex];\n",
" // put the chosen pivot at array[hi]\n",
" swap(array, pivotIndex, hi);\n",
" int storeIndex = lo;\n",
" // Compare remaining array elements against pivotValue = array[hi]\n",
" for (int i = lo; i <= hi - 1; i++) {\n",
" if (compare(pivotValue, array[i])) {\n",
" swap(array, i, storeIndex);\n",
" storeIndex = storeIndex + 1;\n",
" }\n",
" }\n",
" swap(array, storeIndex, hi); // Move pivot to its final place\n",
" return storeIndex;\n",
"}\n",
"\n",
"int choosePivot(int lo, int hi) {\n",
" return (int)Math.ceil((hi + lo) / 2);\n",
"}"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Finally, in the next cell, compare Double Trouble, Bubble, and Quicksort in the numbers of comparisons that they take to sort lists of 100, 1000, 100000, and 1000000 sized arrays.\n",
"\n",
"Sort name | Size | Compares\n",
"----------|------|---------\n",
"Double Trouble | |\n",
"Bubble sort | | \n",
"Quicksort | |"
]
},
{
"cell_type": "markdown",
"metadata": {
"nbgrader": {
"grade": true,
"grade_id": "compare-sorts",
"locked": false,
"points": 50,
"solution": true
}
},
"source": []
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Reflection\n",
"\n"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"*[In the following cell, give a thorough reflection of what you found and learned in this lab. Think outside the box, too. Is there any situation where one sort would be better than another? Then you can remove this cell.]*"
]
},
{
"cell_type": "markdown",
"metadata": {
"nbgrader": {
"grade": true,
"grade_id": "reflection",
"locked": false,
"points": 50,
"solution": true
}
},
"source": []
}
],
"metadata": {
"kernelspec": {
"display_name": "Java 9",
"language": "java",
"name": "java9"
},
"language_info": {
"file_extension": ".class",
"mimetype": "application/java-vm",
"name": "java"
}
},
"nbformat": 4,
"nbformat_minor": 0
}